1. Technical Field
The present invention relates in general to a field of networking, and, in particular, to an improved method and system for classifying data packets.
2. Description of the Related Art
Data being transferred and transmitted across a network, including a network such as the Internet, are typically transmitted in discrete units called packets. A packet is a finite amount of data that is identified by a packet header.
FIG. 1 illustrates a typical system of networks interconnected by routers. Network routers 100, 102 and 104 are gateways that connect two or more distinct computer networks 110, 112, 114, 116, and 118 for the purpose of transferring data packets from one network to another. Typically, network routers 100, 102, and 104 support Internet Protocol (IP) and/or Transmission Control Protocol/Internet Protocol (TCP/IP) network formats. Such routers are typically in compliance with the International Organization for Standardization (ISO) networking model that includes seven layers of functionality, of which the routers deal with four layers: the physical layer, the data link layer, the network layer, and the transport layer (from bottom to top). The other layers, going up the stack, are the session layer, the presentation layer, and the application layer. Each layer conceptually provides function that is used by the next higher layer. A physical layer is directed to the hardware, such as the specifics of how data is transmitted over a certain network medium. The data link layer is concerned with using the physical layer to move data from one machine to another on a single network. The network layer uses the data link layer to move data from one machine to another over different networks.
Referring to FIG. 2, data packet 200 is a basic transmission unit used by networks using the TCP/IP protocol. Information transmitted over a TCP/IP protocol network is encapsulated in a TCP/IP packet 202 before being wrapped in the appropriate link layer headers and trailers, such as media access control (MAC) header 204 and MAC trailer 206 and sent over the network.
In the Open System Interconnection (OSI) networking model, the data link layer can be split into two functions: media access control (MAC) and logical link control (LLC). MAC deals with how to get data into the correct physical form (e.g., electrical voltages) to access the physical layer. LLC handles the addressing of a data packet to get from one piece of hardware to another on the same network. The MAC and LLC layers add a MAC header 204 and a MAC trailer 206, and put the resulting frame on the physical network. (At this level, the data packet, or data gram, is referred to as a frame.) As such, the LLC is a component of the router; and responds to a request from the network layer to send a packet from the system to a remote system by establishing a path to that remote system and returning control to a network layer where a processing of the actual packet contents takes place. In packets utilizing the IP and/or TCP/IP protocol, TCP/IP packet 202 includes both the actual data 220 as well as a TCP/IP “5-tuple” 208. TCP/IP 5-tuple 208 includes IP source address 210, IP destination address 212, TCP source port 214, TCP destination port 216, and IP protocol type 218. Data 202 typically also includes a check sum 222 (for performing check sum error detection), packet length 224 (for giving the length of IP packet 202), and transport control 226 (giving the number of routers the packet has passed through on its way to its destination). It should be noted that individual fields are not illustrated in the order they appear in a packet, but are grouped for convenience of description.
Packet classification is a critical function of all routers. The results of packet classification may be used to determine which of many supported flows a packet should be associated with. This in turn, may affect certain routing decisions, quality of service, traffic shaping or limiting, or even whether or not such packets are forwarded at all. In a general case, packets may be classified using a classification key that includes an arbitrary number of fields. For example, the classification may be based on the TCP/IP 5-tuple 208 described in FIG. 2.
The determination of how a packet should be handled, including prioritization, ultimate destination in the packet, determination of what type server or router the packet should next be directed, is determined by matching a rule to selected parameters of the packet header. A rule is said to match a packet if all of the conditions specified by that rule (in terms of acceptable ranges of values) are met by the actual values in the selected parameters of the packet header. Rule conditions are typically expressed by exact match, prefix match, and range match. That is, a rule may apply to a packet header contains parameter values that fall within a portion of the corresponding parameter ranges defined by the rule. For example, a rule may be focused on the IP source address 210. One rule may route the packet to a particular network if the IP source address 210 is a single specific number, hence there being an exact match. Another rule may direct packets to a particular network if the prefix of the IP source address 210 is the same, thus a prefix match. Alternatively, a rule may direct a packet to a specific network if the IP source address 210 is between a range of numbers, such as 150 to 180, thus having a range match. Similarly, rules may have conditions that are expressed as exact match, prefix match, and/or range match for other components of an IP 5-tuple 208 or other packet header information in an IP packet 202.
Packet classification in general is a difficult problem, requiring significant amounts of storage and multiple accesses to that storage. As networks increase in speed, and the size and complexity of classification rules increase, new techniques must be developed to meet packet processing requirements.
For lower speed applications, tree structures have been applied to the patent classification problem. The number of memory accesses required to follow a chain of pointers to the desired rule grows significantly as a set of classification rules is expanded, limiting the usefulness of this approach. Content-addressable memories (CAM's) are being used for packet classification in certain applications, but they have a somewhat limited memory capacity, and are significantly more expensive than conventional random access memory. On the other hand, CAM's are capable of very high-speed operation, making them very attractive packet classification devices for higher speed routers.
Therefore, there is a need for a method and system to categorize packet header information while minimizing the amount of memory required.